package LeetCode;

import java.util.Scanner;

/**
 * @Classname LeetCode.BigNumMultiple
 * @Description TODO
 * @Date 2020/9/29 10:47
 * @Created by wwk
 * @Author wwk
 */
public class BigNumMultiple {

    static int plusMinus(int x,int y){
        if(x>=0&&y>=0){
            return 1;
        }else{
            return -1;
        }
    }
    public static int divideConquer(int X, int Y, int n){
        int flag=plusMinus(X,Y);
        int x=Math.abs(X);
        int y=Math.abs(Y);
        if(X==0||Y==0){
            return 0;
        }else if(n==1){
            return flag*x*y;
        }else{
            int A=(int)(x/Math.pow(10,(int)n/2));
            int B=(int)(x - A * Math.pow(10,(int)n/2));
            int C=(int)(y/Math.pow(10,(int)n/2));
            int D=(int)(y - C * Math.pow(10,(int)n/2));
            int AC = divideConquer(A, C, n / 2);
            int BD = divideConquer(B, D, n / 2);
            int ABDC = divideConquer((A - B), (D - C), n / 2) + AC + BD;
            return flag * (int)(AC * Math.pow(10 , n) + ABDC * Math.pow(10, (int)(n / 2)) + BD);
        }
    }

    public static void main(String[] args) {
        int x, y, n;
        System.out.println("请输入两个大数和大数的位数：");
        x=new Scanner(System.in).nextInt();
        y=new Scanner(System.in).nextInt();
        n=new Scanner(System.in).nextInt();
        System.out.println("计算得"+divideConquer(x,y,n));
    }
}
